Theo Bắc Tề thư, tổ tịch Cao Hoan ở huyện Điệu, quận Bột Hải (nay thuộc huyện Cảnh, Hà Bắc, Trung Quốc): "Tổ 6 đời tên Ẩn, từng làm Thái thú Huyền Thố đời Tấn. Ẩn sinh Khánh, Khánh sinh Thái, Thái sinh Hồ, 3 đời làm quan cho nhà Mộ Dung"[1]. Tổ phụ là Cao Mật bị lưu đày đến trấn Hoài Sóc, từ đó định cư tại đây. Hoài Sóc là một trong sáu binh trấn nhà Bắc Ngụy thành lập để phòng bị người Nhu Nhiên ở phía bắc, hợp xưng là Lục trấn. Gia tộc Cao Hoan đến đời của ông đã bị Tiên Ti hóa. Bản thân Cao Hoan cũng có tên Tiên Ti là Heliuhun (賀六渾，Hạ Lục Hồn)

Cha Hoan là Cao Thụ, mẹ Hàn thị. Mẹ mất sớm, Hoan phải ở với người chị và anh rể là Úy Cảnh. Nhà nghèo, Hoan đi làm thuê ở Bình Thành, Đại Quận, được con gái gia đình giàu có trong thành là Lâu Chiêu Quân phải lòng, nhất quyết lấy, dù gia đình ngăn cản. Nhờ tiền vợ, Hoan mua được ngựa, chuyển nghề sang chạy dịch trạm chuyển văn thư giữa Bình Thành và Lạc Dương.

Khi loạn Lục trấn bùng phát, năm 525, Hoan theo phò Đỗ Lạc Chu, sau khi Lạc Chu bị giết, Hoan theo Cát Vinh. Năm 528, Hoan bỏ Cát Vinh về với Nhĩ Chu Vinh, nhờ có bạn cũ là Lưu Quý tiến cử. Ông tướng mạo tầm thường, vẫn bị Nhĩ Chu Vinh xem thường. Về sau có lần thấy ông trị được ngựa chứng, Nhĩ Chu Vinh từ đó xem trọng ông.